1. Field of the Invention
The present invention relates to an add/compare/select (ACS) processor using the same in Viterbi decoder, and more particularly to an ACS processor for performing add/compare/select process with respect to a plurality of states in one processing element by grouping N number of processing elements for corresponding N number of states into a predetermined processing element units using the same branch metric and state metric.
2. Description of the Prior Art
In general, a Viterbi algorithm is used as a practical and efficient method for a maximum-likelihood decoding of convolutional codes. In the Viterbi algorithm, path distances of two different paths which meet at an arbitrary state are compared by using a trellis diagram. By the comparison, the path with a shorter distance, namely a path of the lowest error generation probability is selected as a survivor path. A Viterbi decoder using the Viterbi algorithm is, for example, used for error correction in satellite communication systems, since the decoder has a high random error correction capability.
Referring to FIGS. 1A and 1B, the Viterbi algorithm will be described in detail. FIG. 1A shows a trellis diagram in which the number of node and state is 2. Its vertical and horizontal directions represent the state S.sub.i (i=1, 2) and time (t/T: here, 1/T represents a transmission rate), respectively, and S.sub.i,k represents (i)th state at time k. A Finite State Machine selects an arbitrary path through the trellis diagram illustrated in FIG. 1A, and calculates a branch metric .lambda. for a time interval (k, k+1) according to a transition of the observed state. Namely, by the trellis diagram, the states (S.sub.1,k, S.sub.2,k) at the time k are connected with the states (S.sub.1,k+1, S.sub.2,k+1) at the time k+1 by each branch for the time interval (k, k+1). During Viterbi decoding, a distance between the codes at the branch corresponding to received signals, namely the branch metric, is calculated. The branch metric becomes a hamming distance for a hard decision decoding, and an Euclidean distance for a soft decision decoding.
By using the calculated branch metric, a new path metric for each node at the time k+1 is calculated according to a path metric .gamma. at time k and the branch metric .lambda. at the time interval (k, k+1). This calculation will be described in detail by referring to FIG. 1B.
In FIG. 1B, the nodes S.sub.1,k, S.sub.2,k at time k have the path metrics .gamma..sub.1,k, .gamma..sub.2,k, which are the accumulation of its branch metrics, respectively. When the branch metrics for the time interval (k, k+1) are .lambda..sub.11,k, .lambda..sub.12,k, .lambda..sub.21,k, .lambda..sub.22,k, new path metrics .gamma..sub.1, k+1, .gamma..sub.2, k+1 of the nodes S.sub.1,k+1, S.sub.2,k+1 at time k+1 are obtained by the following expression 1.
Expression 1.
.gamma..sub.1, k+1 =max .lambda..sub.11,k +.gamma..sub.1,k, .lambda..sub.12,k +.gamma..sub.2,k ! PA1 .gamma..sub.2, k+1 =max .lambda..sub.21,k +.gamma..sub.1,k, .lambda..sub.22,k +.gamma..sub.2,k ! PA1 N number of processing elements for receiving two path metrics and two branch metrics, comparing each added values, and outputting two decision bits and two state metrics according to a compared result; PA1 a grouping unit for grouping N number of processing elements for corresponding N number of states into processing elements of K number of units using the same state metrics and the same branch metrics; PA1 a multiplexer for multiplexing L (L=2K) number of path metrics provided from the grouped result into two path metrics according to a predetermined clock signal, and outputting them to a corresponding processing element of the N number of processing elements; PA1 a first demultiplexer for receiving two decision bits obtained from the corresponding processing element, and demultiplexing them into L number of decision bits according to the clock signal; and PA1 a second demultiplexer for receiving two state metrics obtained from the corresponding processing element, and demultiplexing them into L number of state metrics according to the clock signal.
Namely, a plurality of paths with a variation of states at time k lead to the node at time k+1, and utilizing a probability information of a branch metric, the path metric is determined. The process for calculating the path metric is performed recursively for each time k to determine a final survivor path.
When the survivor paths are traced back, the paths merge at an arbitrary point in time with high probability, as shown in FIG. 1B. The number of time steps which merge at the point with high probability is a survivor depth, and it determines the latency of the Viterbi decoding. Namely, when the path metrics .gamma. are updated by the expression 1 at each node, they retain the states of the corresponding paths prior to reaching the survivor depth. Accordingly, the variations of the states prior to the survivor depth, which are obtained by the trace back, are outputted as a Viterbi-decoded data.
FIG. 2 shows a block diagram of a conventional Viterbi decoder. The Viterbi decoder comprises a branch metric generator 100, an ACS unit 200, and a survivor memory 300.
In FIG. 2, the branch metric generator 100 receives a convolutionally-coded data, and calculates a branch metric .lambda..sub.ij, k, which is a distance between codes on each branch corresponding to a received signal. At this time, the complexity of the branch metric generation unit 100 is directly related to the length of received code word. As the number of bit comprising code words increases, the more complex circuit is required. For example, when the code words are composed of 2-bits, the number of comparison code words needed for comparing received code words of 2-bits are 2.sup.2 or 4. If, the code words are composed of 3-bits, the number of comparison code words needed for comparing received code words of 3-bits are 2.sup.3 or 8. Additionally, the branch metric values calculated with respect to the longer code words are larger. Consequently, as the memory capacity for storing corresponding branch metrics increases as much as the increase in the branch metric values and the number of comparison code words, it leads to the structural complexity of ACS unit 200.
The ACS unit 200 receives the branch metrics from the branch metric generator 100, adds them to the previous path metric and determines a multitude of candidate paths. The ACS unit 200 then compares the multitude of candidate path metric values, and selects a path having the shortest path metric, and outputs the newly selected path metric and the compared result, namely the decision bit. ACS unit 200 updates the path metric by using the branch metric obtained from the branch metric generator 100 at each decoding cycle, and outputs the decision bit of N-bits to the survivor memory 300. Accordingly, when trellis diagram comprises total of N number of states, N-bits are obtained from each decoding cycle.
The survivor memory 300 stores the decision bit obtained from the ACS unit 200, recovers the original information sequence by using the decision bit, and outputs it as a Viterbi-decoded data.
FIG. 3 shows a block diagram of a processing element 310 of the ACS unit 200 illustrated in FIG. 2. The processing element 310 comprises largely a first processor 320 and a second processor 340. Here, the first processor 320 comprises a first adder 322, a second adder 324, a first comparator 326, and a first selector 328. The second processor 340 comprises a third adder 342, a fourth adder 344, a second comparator 346, and a second selector 348.
In FIG. 3, .gamma..sub.X and .gamma..sub.Y represent path metrics inputted into the processing element 310, respectively, and here the path metric of 6-bits is taken as an example to show the operation of the processing elements. The path metric .gamma..sub.X is inputted into the first adder 322 of the first processor 320 and the third adder 342 of the second processor 340. The path metric .gamma..sub.Y is inputted into the second adder 324 of the first processor 320 and the fourth adder 344 of the second processor 340. The branch metrics .lambda..sub.X and .lambda..sub.Y are provided from the branch metric generator 100 in FIG. 2, and the branch metric of 4-bits is taken as an example here. The branch metric .lambda..sub.X is inputted into the first adder 322 of the first processor 320 and the fourth adder 344 of the second processor 340. The branch metric .lambda..sub.Y is inputted into the second adder 324 of the first processor 320 and the third adder 342 of the second processor 340. The first and second decision bits outputted from the first and second comparators 326 and 346 of the first and second processors 320 and 340, respectively, are provided to the survivor memory 300 in FIG. 2.
Referring to FIG. 3, an operation of the processing element 310 of the ACS unit 200 will be described in detail.
In view of the first processor 320, the first adder 322 adds the path metric .gamma..sub.X to the branch metric .lambda..sub.X, and outputs the added value to the first comparator 326 and the first selector 328, respectively. The second adder 324 adds the path metric .gamma..sub.Y to the branch metric .lambda..sub.Y, and outputs the added value to the first comparator 326 and the first selector 328, respectively.
The first comparator 326 compares the added value from the first adder 322 to the added value from the second adder 324, and outputs the compared result, namely a first decision bit to the first selector 328 as a selection signal to the survivor memory 300 in FIG. 2. For example, when the added value from the first adder 322 is larger than the added value from the second adder 324, the first comparator 326 outputs the first decision bit "0". When the added value from the first adder 322 is smaller than the added value from the second adder 324, the first decision bit "1" is outputted.
The first selector 328 selectively outputs the added value from the first adder 322 or the added value from the second adder 324 according to the selection signal. Namely, the first selector 328 selects the added value from the second adder 324 to output it as the state metric when the first decision bit is "0", whereas it selects the added value from the first adder 322 to output it as the state metric when the first decision bit is "1".
In view of the second processor 340, the third adder 342 adds the path metric .gamma..sub.X to branch metric .lambda..sub.Y, and outputs the added value to the second comparator 346 and the second selector 348, respectively. The fourth adder 344 adds the path metric .gamma..sub.Y to branch metric .lambda..sub.X, and outputs the added value to the second comparator 346 and the second selector 348, respectively.
The second comparator 346 compares the added value from the third adder 342 to the added value from the fourth adder 344, and outputs the compared result, namely the second decision bit to the second selector 348 as a selection signal and the survivor memory 300 in FIG. 2, respectively. For example, when the added value from the third adder 342 is larger than the added value from the fourth adder 344, the second comparator 346 outputs the second decision bit "0". When the added value from the third adder 342 is smaller than the added value from the fourth adder 344, the second decision bit "1" is outputted.
The second selector 348 selectively outputs the added value from the third adder 342 or the added value from the fourth adder 344 according to the selection signal. Namely, the second selector 348 selects the added value from the fourth adder 344 to output it as the state metric when the second decision bit is "0", whereas it selects the added value from the third adder 342 to output it as the state metric when the second decision bit is "1".
It is possible to combine, by grouping, the two processing elements using to same state metric into an one processing element as shown in FIG. 3. Namely, one processing element performs add/compare/select processing for two states. Hence, in case of 64 states, ACS processor needs 32 processing elements PE0 through PE31.
The above ACS processor is an improved version to the ACS processor which processes one state in one processing element, however, it leaves much to be desired. Recently, as the technology for Application Specific Integrated Circuits (ASIC) has rapidly advanced, there is a need to decrease the size of the hardware when designing ASIC by processing at least more than two states in one processing element.